package 记忆化搜索;

import java.util.Arrays;

//63 不同路径2
public class Solution7 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if(obstacleGrid[row-1][col-1]==1) return 0;
        mem = new int[row][col];
        for(int i=0;i<row;i++){
            Arrays.fill(mem[i],-1);
        }
        return dfs(0,0,row,col,obstacleGrid);
    }
    int[][] mem;
    int dfs(int i, int j, int row, int col, int[][]obstacleGrid){
        if(i==row-1&&j==col-1) return 1;
        if(i>=row||j>=col||obstacleGrid[i][j]==1) return 0;
        if(mem[i][j]!=-1) return mem[i][j];
        return mem[i][j] = dfs(i+1,j,row,col,obstacleGrid)+dfs(i,j+1,row,col,obstacleGrid);
    }
}
